SYNTHESIS OF CIRCUITS CONTAINING UNRELIABLE GATES IN Pk

Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia), alehina@pnzgu.ru

519.718

Background. Мultivalued logic gives ample opportunities for creation of various algorithms in many fields and can be successfully applied in solving problems and in multiple technical developments. This explains the interest to the problem of build-ing reliable circuits in the complete finite basis of k-valued functions (k ≥ 3), which is solved with k equaling to 3 and 4. The aim of the work is to reveal features of k-valued functions (k ≥ 5), the circuits of which may be used for improvement of initial circuits’ reliability, and to describe the corresponding synthesis method.
Materials and methods. The study included well-known methods of discrete math-ematics and mathematical cybernetics for obtaining circuit unreliability values and for estimating a number of functions of a special type. Besides, the author suggests a new method of synthesizing circuits containing unreliable functional elements.
Results. The author revealed k-valued functions (k ≥ 5), the circuits that can be used for improvement of initial circuits’ reliability, and described the corresponding synthesis method. The researcher obtained the upper and the lower values for a num-ber of such functions.
Conclusions. Features of three-valued and four-valued functions, revealed previ-ously, circuits that can be used for improvement of initial circuits’ reliability may be generalized in case of k-valued functions at any natural k ≥ 5.

k-valued logic functions, unreliable functional gates, synthesis of circuits containing unreliable gates.

1. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2010, no. 1 (13), pp. 64–79.
2. Alekhina M. A. Diskretnaya matematika [Discrete mathematics]. 2012, vol. 24, no. 3, pp. 17−24.
3. Alekhina M. A. Fundamenta Informaticae [Fundamental informatics]. 2010, vol. 104 (3), pp. 219–225.
4. Grabovskaya S. M. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2011, no. 3 (19), pp. 52–60.
5. Vinogradov Yu. A. Matematicheskie voprosy kibernetiki: sb. st. Vyp. 3. [Mathematical problems of cybernetics: collected papers. Issue 3]. Moscow: Nauka, 1991, pp. 187–198.
6. Vinogradov Yu. A. Matematicheskie voprosy kibernetiki: sb. st. Vyp. 8. [Mathematical problems of cybernetics: collected papers. Issue 8]. Moscow: Nauka, 1999, pp. 298–300.
7. Barsukova O. Yu. Sintez nadezhnykh skhem, realizuyushchikh funktsii dvuznachnoy i trekhznachnoy logik: dis. kand. fiz.-mat. nauk [Synthesis of reliable circuits, realizing functions of two-valued and three-valued logic: dissertation to apply for the degree of the candidate of physical and mathematical sciences]. Penza, 2014, 87 p.
8. Alekhina M. A., Barsukova O. Yu. Diskretnyy analiz i issledovanie operatsiy [Discrete analysis and research of operations]. 2014, vol. 21, no. 4, pp. 12–24.
9. Alekhina M. A., Kargin S. P. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2014, no. 4 (32), pp. 47–56.